#define _CRT_SECURE_NO_WARNINGS

#include<iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};
 
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (!head)
            return head;
        ListNode* pcur = head;
        int node_digit = 0;
        while (pcur) {
            pcur = pcur->next;
            ++node_digit;
        }
        int n = node_digit;
        while (--n) {
            pcur = head;
            ListNode* prev = nullptr;
            /*for (int i = 0; i < node_digit - n - 1; i++) {
                prev = pcur;
                pcur = pcur->next;
            }*/
            prev = nullptr;
            pcur = head;
            for (int i = 0; i < n; i++) {
                if (pcur->val > pcur->next->val) {
                    if (prev == nullptr) {
                        head = pcur->next;
                        pcur->next = head->next;
                        head->next = pcur;
                        prev = head;
                    }
                    else {
                        ListNode* pnext = pcur->next;
                        prev->next = pnext;
                        pcur->next = pnext->next;
                        pnext->next = pcur;
                        pcur = pnext;
                        prev = pcur;
                        pcur = pcur->next;
                    }
                }
                else {
                    prev = pcur;
                    pcur = pcur->next;
                }
            }
        }
        return head;
    }
};

int main()
{
    ListNode a(-1);
    ListNode b(5);
    ListNode c(3);
    ListNode d(4);
    ListNode e(0);
    a.next = &b;
    b.next = &c;
    c.next = &d;
    d.next = &e;
    ListNode* head = Solution().sortList(&a);
    while (head) {
        cout << head->val << endl;
        head = head->next;
    }
    return 0;
}